Skip to content

geeksforgeeks Stack Data Structure

NOTE:

1、这篇文章，整理地非常好

Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).

img

There are many real-life examples of a stack. Consider an example of plates stacked over one another in the canteen. The plate which is at the top is the first one to be removed, i.e. the plate which has been placed at the bottommost position remains in the stack for the longest period of time. So, it can be simply seen to follow LIFO(Last In First Out)/FILO(First In Last Out) order.

Topics :

Introduction :

  1. Introduction to Stack
  2. Stack in C++ STL
  3. Stack Class in Java
  4. Stack in Python
  5. Stack in C#

Design and Implementation :

  1. Implement Queue using Stacks
  2. Design and Implement Special Stack Data Structure | Added Space Optimized Version
  3. Implement two stacks in an array
  4. Implement Stack using Queues
  5. Design a stack with operations on middle element
  6. How to efficiently implement k stacks in a single array?
  7. How to create mergable stack?
  8. Design a stack that supports getMin() in O(1) time and O(1) extra space
  9. Implement a stack using single queue
  10. How to implement stack using priority queue or heap?
  11. Create a customized data structure which evaluates functions in O(1)
  12. Implement Stack and Queue using Deque

Standard Problems based on Stack :

NOTE:

一、fix conversion

二、Expression Evaluation

三、括号匹配

1、Infix to Postfix Conversion using Stack

2、Prefix to Infix Conversion

3、Prefix to Postfix Conversion

4、Postfix to Prefix Conversion

5、Postfix to Infix

6、Convert Infix To Prefix Notation

7、The Stock Span Problem

NOTE:

1、股票价格跨度

8、Check for balanced parentheses in an expression

9、Next Greater Element

10、Next Greater Frequency Element

11、Number of NGEs to the right

12、Maximum product of indexes of next greater on left and right

13、The Celebrity Problem

14、Expression Evaluation

15、Arithmetic Expression Evalution

16、Evaluation of Postfix Expression

17、Iterative Tower of Hanoi

18、Print next greater number of Q queries

Operations on Stack :

  1. Reverse a stack using recursion
  2. Sort a stack using recursion
  3. Sort a stack using a temporary stack
  4. Reverse a stack without using extra space in O(n)
  5. Delete middle element of a stack
  6. Sorting array using Stacks
  7. Delete array elements which are smaller than next or become smaller
  8. Check if a queue can be sorted into another queue using a stack
  9. Reverse individual words
  10. Count subarrays where second highest lie before highest
  11. Check if an array is stack sortable

Misc :

  1. Iterative Postorder Traversal | Set 1 (Using Two Stacks)
  2. Iterative Postorder Traversal | Set 2 (Using One Stack)
  3. Merge Overlapping Intervals
  4. Largest Rectangular Area in a Histogram | Set 2
  5. Print ancestors of a given binary tree node without recursion
  6. Reverse a string using stack
  7. Program for Tower of Hanoi
  8. Find maximum depth of nested parenthesis in a string
  9. Find maximum of minimum for every window size in a given array
  10. Length of the longest valid substring
  11. Iterative Depth First Traversal of Graph
  12. Minimum number of bracket reversals needed to make an expression balanced
  13. Expression contains redundant bracket or not
  14. Identify and mark unmatched parenthesis in an expression
  15. Check if two expressions with brackets are same
  16. Find index of closing bracket for a given opening bracket in an expression
  17. Check for balanced parentheses in an expression
  18. Balanced expression with replacement
  19. Check if a given array can represent Preorder Traversal of Binary Search Tree
  20. Form minimum number from given sequence
  21. Find if an expression has duplicate parenthesis or not
  22. Find maximum difference between nearest left and right smaller elements
  23. Find next Smaller of next Greater in an array
  24. Find maximum sum possible equal sum of three stacks
  25. Count natural numbers whose all permutation are greater than that number
  26. Delete consecutive same words in a sequence
  27. Decode a string recursively encoded as count followed by substring
  28. Bubble sort using two Stacks
  29. Pattern Occurrences : Stack Implementation Java
  30. Iterative method to find ancestors of a given binary tree
  31. Stack Permutations (Check if an array is stack permutation of other)
  32. Tracking current Maximum Element in a Stack
  33. Check mirror in n-ary tree
  34. Reverse a number using stack
  35. Reversing the first K elements of a Queue
  36. Reversing a Queue
  37. Check if stack elements are pairwise consecutive
  38. Spaghetti Stack
  39. Interleave the first half of the queue with second half
  40. Remove brackets from an algebraic string containing + and – operators
  41. Growable array based stack
  42. Range Queries for Longest Correct Bracket Subsequence