LEC-1 STACK & QUEUE

LIFO the stack works on

push , pop , top, size
push(2), push(1), push(3), push(4), pop -> top -> pop -> top ->push
on the first pop command the first that came in will go out i.e. 2

Stack

1 // Note: This file demonstrates STACK operations (LIFO - Last In First

Out)
2 // Queue works on FIFO (First In First Out) principle
3 // Queue operations: push(enqueue), pop(dequeue), front, size
4 // Stack operations: push, pop, top, size
5
6 // Example walkthrough:
7 // push(2), push(1), push(3), push(4), pop -> top -> pop -> top -> push
8 // For queue: first pop would remove 2 (first element inserted)
9 // For stack: first pop would remove 4 (last element inserted)
10
11 #include <bits/stdc++.h> // Include all standard libraries
12 using namespace std; // Use standard namespace
13
14 int main(){
15 // Declare a stack of integers (Note: using stack, not queue)
16 stack<int> s;
17
18 // Push elements onto the stack
19 s.push(10); // Bottom element
20 s.push(20); // Middle element
21 s.push(30); // Top element (last in, first out)
22
23 // Display the top element of the stack
24 cout<<"Top element: "<< s.top()<<endl; // Will print 30
25
26 // Display current size of the stack
27 cout<<"The size of the stack is: "<<s.size()<<endl; // Will print 3
28
29 // Remove the top element from the stack
30 s.pop(); // Removes 30 (top element)
31
32 // Display size after pop operation
33 cout<< "After pop, the size of the stack is: "<< s.size()<<endl; //
Will print 2
34
35 return 0; // Indicate successful program execution
36 }

Stack using array

1 // stack_array.cpp
2 // Compile with: g++ -std=c++17 stack_array.cpp -O2 -o stack_array
3 #include <iostream>
4 #include <iomanip> // for formatting (optional)
5
6 using namespace std;
7
8 #define MAX 100 // Maximum capacity of the stack (change as needed)
9
10 /*
11 Class invariant:
12 - `top` is the index of the current top element.
13 - When stack is empty: top == -1
14 - When stack has n elements: top == n-1 (0 <= top < MAX)
15 - Valid elements are stored in arr[0..top]
16 */
17 class Stack {
18 private:
19 int arr[MAX]; // underlying container (fixed-size array)
20 int top; // index of top element; -1 means empty
21
22 public:
23 // Constructor: creates an empty stack
24 Stack() : top(-1) { }
25
26 // Check whether the stack is empty (O(1))
27 // Precondition: none
28 // Postcondition: returns true iff there are no elements in the
stack
29 bool isEmpty() const {
30 return top == -1;
31 }
32
33 // Check whether the stack is full (O(1))
34 // Precondition: none
35 // Postcondition: returns true iff there is no more capacity to push
36 bool isFull() const {
37 return top == MAX - 1;
38 }
39
40 // Push a value onto the stack (O(1))
41 // Precondition: stack should not be full
42 // Postcondition: top increases by 1 and arr[top] == value
43 // On overflow: this implementation prints an error and does
nothing.
44 // Alternative: throw an exception or return a boolean to signal
failure.
45 void push(int value) {
46 if (isFull()) {
47 cerr << "Stack Overflow! Cannot push " << value << '\n';
48 return;
49 }
50 arr[++top] = value; // increment top, then store value
51 // After this: arr[top] == value and top >= 0
52 }
53
54 // Pop the top element and return it (O(1))
55 // Precondition: stack should not be empty
56 // Postcondition: top decreases by 1 and the previous top value is
returned
57 // On underflow: prints an error and returns a sentinel (-1).
58 // NOTE: returning -1 may conflict with valid data; see improved
alternative below.
59 int pop() {
60 if (isEmpty()) {
61 cerr << "Stack Underflow! Cannot pop\n";
62 return -1; // sentinel/error value; consider alternatives
63 }
64 return arr[top--]; // return current top and then decrement top
65 }
66
67 // Peek (inspect) current top element without removing it (O(1))
68 // Precondition: stack should not be empty
69 // Postcondition: returns arr[top], stack unchanged
70 // On empty: prints an error and returns sentinel -1.
71 int peek() const {
72 if (isEmpty()) {
73 cerr << "Stack is empty! peek() not available\n";
74 return -1;
75 }
76 return arr[top];
77 }
78
79 // Return current number of elements in the stack (O(1))
80 size_t size() const {
81 return static_cast<size_t>(top + 1);
82 }
83
84 // Display contents from bottom to top — helpful for debugging
(O(n))
85 void display() const {
86 if (isEmpty()) {
87 cout << "Stack is empty!\n";
88 return;
89 }
90 cout << "Stack (bottom -> top): ";
91 for (int i = 0; i <= top; ++i) {
92 cout << arr[i];
93 if (i != top) cout << " ";
94 }
95 cout << "\n";
96 }
97 };
98
99 // -------------------- Demonstration in main() --------------------
100 int main() {
101 Stack s;
102
103 cout << "Pushing values: 10, 20, 30\n";
104 s.push(10);
105 s.push(20);
106 s.push(30);
107
108 cout << "Current top: " << s.peek() << " (expected 30)\n";
109 cout << "Current size: " << s.size() << " (expected 3)\n";
110
111 cout << "Popping: " << s.pop() << " (expected 30)\n";
112 cout << "Now top: " << s.peek() << " (expected 20)\n";
113
114 s.display(); // should show: 10 20
115
116 // Show error handling for pop on empty stack:
117 cout << "\nEmptying the stack...\n";
118 s.pop(); // pops 20
119 s.pop(); // pops 10
120 s.pop(); // underflow -> prints error and returns -1 sentinel
121
122 return 0;
123 }

another way of implementing stack with array

1 #include <bits/stdc++.h>
2 using namespace std;
3 #define MAX 100
4
5 class Stack{
6 public:
7 int *arr;
8 int size;
9 int top;
10
11 Stack(int size){
12 this -> size = size;
13 arr = new int[size];
14 top = -1;
15 }
16
17 bool isEmpty(){
18 return top == -1;
19 }
20
21 bool isFull(){
22 return top == size -1;
23 }
24
25 void push(int element){
26 if(isFull()){
27 cout<<"stack overflow!!"<<endl;
28 }
29 top++;
30 arr[top] = element;
31
32 }
33
34 void pop(){
35 if(isEmpty()){
36 cout<<"Stack underflow!!"<<endl;
37 }
38 top--;
39 }
40
41
42 int peek(){
43 if(top>=0){
44 return arr[top];
45 }
46 else{
47 cout<<"Stack is empty" <<endl;
48 return -1;
49 }
50
51 }
52 };
53
54
55 int main(){
56 Stack s(5);
57 s.push(22);
58 s.push(43);
59 s.push(44);
60
61 cout<<s.peek()<<endl;
62 s.pop();
63 cout<<s.peek()<<endl;
64 s.pop();
65 cout<<s.peek()<<endl;
66 s.pop();
67 cout<<s.peek()<<endl;
68 cout<<s.isEmpty()<<endl;
69 return 0;
70 }
71