stack data type (tsz. stack data types)
| Művelet | Szignatúra | Leírás |
|---|---|---|
| create | Stack<T> S;
|
Üres verem létrehozása. |
| push(x) | S.push(x)
|
x elem beszúrása a verem tetejére.
|
| pop() | S.pop()
|
A verem tetejéről eltávolítja a legfelső elemet. |
| top() / peek() | T y = S.top()
|
Visszaadja (de nem távolítja el) a verem tetején álló elemet. |
| isEmpty() | bool b = S.empty()
|
Igaz, ha a verem üres. |
| size() | size_t n = S.size()
|
A veremben jelenleg tárolt elemek száma. |
| clear() | (nem szabványos, de gyakori) | Az összes elem törlése. |
Adatszerkezet:
template<typename T>
class Stack {
T* data; // dinamikus tömb
size_t cap; // tömb kapacitása
size_t topIndex; // a következő szabad hely indexe (vagy a tető indexe +1)
public:
Stack(): data(new T), cap(initial), topIndex(0) {}
void push(const T& x) {
if(topIndex == cap) resize(cap*2);
data = x;
}
void pop() { if(topIndex>0) --topIndex; }
T& top() { return data; }
bool empty() const { return topIndex==0; }
size_t size() const { return topIndex; }
// resize(), destructor, etc.
};
Komplexitás:
push: amortizált O(1) (szükség esetén tömb‐másolás O(n)),pop: O(1),top: O(1),size/empty: O(1).
Adatszerkezet: minden csomópont mutat a következőre, a verem teteje a head.
template<typename T>
class Stack {
struct Node { T value; Node* next; };
Node* head;
size_t count;
public:
Stack(): head(nullptr), count(0) {}
void push(const T& x) {
head = new Node{x, head};
++count;
}
void pop() {
Node* tmp = head;
head = head->next;
delete tmp;
--count;
}
T& top() { return head->value; }
bool empty() const { return head==nullptr; }
size_t size() const { return count; }
~Stack(){ while(head) pop(); }
};
Komplexitás:
push, pop, top, empty, size mind O(1).
C++ STL
#include <stack>
std::stack<int> s;
s.push(42);
int x = s.top();
s.pop();
bool b = s.empty();
Alapértelmezett belső összeállítás: deque<T>, de lehet vector<T> vagy list<T> is.
Java
Deque<Integer> st = new ArrayDeque<>();
st.push(42); // vagy st.addFirst(42)
int x = st.peek(); // teteje
st.pop(); // eltávolítja
boolean b = st.isEmpty();
(A klasszikus java.util.Stack régi, helyette Deque ajánlott.)
Python
stack =
stack.append(42)
x = stack
stack.pop()
empty = not stack
undo‐kor pop, redo‐kor push.
pop/top üres veremnél hívódik, kezelendő (hiba, kivétel, vagy guard condition).
A Stack ADT egy rendkívül egyszerű, de kulcsfontosságú adatszerkezet a LIFO viselkedés modellálására. A két leggyakoribb implementáció tömb‐ vagy láncolt lista‐alapú, mindkettő O(1) műveleteket biztosít, és beépített támogatása van a legtöbb nyelv standard könyvtáraiban. A stack számos algoritmus és alkalmazás alapeleme: kifejezéskiértékelés, keresés, undo/redo, visszalépéses keresés, rekurszió iteratív helyettesítése.