Stacks And Queues
Go to ProblemsStack Implementation Details
C :
Stack declaration : :
int A[MAX_SIZE]; // create a integer array of maximum expected size for the stack
int *A = (int *) malloc(1000 * sizeof(int)); // or malloc it.
int size = 0; // Also keep track of the current size
Push
A[size++] = newElement; // Put the new Element on the end of the array. O(1).
Pop
size--; // Simply reduce the size. O(1)
isEmpty
return (size == 0); // Check if size is 0. O(1)
Size
return size; // 'size' tracks the current size of the stack.
Top
A[size - 1]
C++ :
C style array stack works in C++ as well. However, C++ provides a library implementation of stack as well.
Stack declaration : :
stack<int> A; // declares an empty stack.
Push
A.push(newElement); // Pushes a new element. O(1)
Pop
A.pop(); // O(1) pop
isEmpty
A.empty() // O(1)
Size
A.size(); // O(1)
Top
A.top(); // O(1). Gives the top element.
JAVA :
Java has a stack similar to C++.
Stack declaration : :
Stack<Integer> A = new Stack<Integer>();
Push
A.push(new Integer(newElement)); // Pushes a new element. O(1)
Pop
A.pop(); // O(1) pop
isEmpty
A.empty() // O(1)
Size
A.size(); // O(1)
Top
A.peek(); // O(1). Gives the top element.
PYTHON :
We can use list as a stack in python. Very similar to how we do it in C.
Stack declaration : :
A = [] # declares an empty stack. O(1)
Push
A.append(newElement) # Put the new Element on the end of the array. O(1).
Pop
A.pop() # removes the last element. O(1)
isEmpty
return (len(A) == 0); # Check if size is 0. O(1)
Size
return len(A); # O(1)
Top
A[-1] # O(1)
Walkthrough examples :
Stacks And Queues Problems
Stack simple
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Balanced Parantheses! | 200 |
|
15:59 | |
| Simplify Directory Path | 250 |
|
54:00 | |
| Redundant Braces | 300 |
|
42:41 | |
| Min Stack | 400 |
|
43:31 |
Cleverstack
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| MAXSPPROD | 200 |
|
88:22 | |
| Nearest Smaller Element | 350 |
|
41:37 | |
| Largest Rectangle in Histogram | 450 |
|
65:52 |
Bfs
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Hotel Service | 200 |
|
47:23 |
Queue
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| First non-repeating character in a stream of characters | 200 |
|
58:44 | |
| Sliding Window Maximum | 450 |
|
69:38 |
Stack math
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Evaluate Expression | 400 |
|
32:46 | |
| Rain Water Trapped | 400 |
|
59:06 |
