Explain how to implement two stacks in one array A[1..n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The PUSH and POP operations should run in O(1) time.
The code is implemented in C++.
/* * File: main.cpp * Author: bekoC */ #include <cstdlib> #include<stdio.h> #include <stdlib.h> #include<iostream> #define N 10 struct Stacks { char charArray[N]; int top1, top2; void olustur(); bool Insert(int stackNumber, char veri); char deleteFromStack(int stackNumber); bool isEmpty(int stackNumber); void printStack(int stackNumber); }; bool Stacks::Insert(int stackNumber, char newChar) { if (top1 == top2) { return false; } if (stackNumber == 1) charArray[top1++] = newChar; else charArray[top2--] = newChar; return true; } char Stacks::deleteFromStack(int stackNumber) { if (stackNumber == 1) return charArray[--top1]; else return charArray[++top2]; } bool Stacks::isEmpty(int stackNumber) { if (stackNumber == 1) return (top1 == 0); else return (top2 == N - 1); } void Stacks::create() { top1 = 0; top2 = N - 1; } void Stacks::printStack(int stackNumber) { if (stackNumber == 1 && !isEmpty(stackNumber)) { { for (int i = 0; i <= top1; ++i) { printf("%c", charArray[i]); } } } else if (isEmpty(stackNumber)) { printf("Stack 1 is empty"); } if (stackNumber == 2 && !isEmpty(stackNumber)) { for (int i = N - 1; i >= top2; i--) { printf("%c", charArray[i]); } } else if (isEmpty(stackNumber)) { printf("Stack 2 is empty"); } } int main() { Stacks myStack; myStack.create(); myStack.Insert(1, 'A'); myStack.Insert(1, 'B'); myStack.Insert(1, 'C'); myStack.Insert(1, 'D'); myStack.Insert(1, 'E'); myStack.Insert(1, 'F'); myStack.Insert(2, 'W'); myStack.Insert(2, 'X'); myStack.Insert(2, 'Y'); myStack.Insert(2, 'Z'); myStack.printStack(1); myStack.printStack(2); if (!myStack.isEmpty(1)) myStack.deleteFromStack(1); if (!myStack.isEmpty(2)) myStack.deleteFromStack(2); return 0; }
No comments:
Post a Comment