stack data type

Angol

Főnév

stack data type (tsz. stack data types)

1. (informatika) A Stack ADT (Abstract Data Type) egy LIFO (Last‐In, First‐Out) szemléletű konténer, melynek fő jellemzője, hogy az utoljára betett elem kerül először ki. A stack-et gyakran használjuk rekurzív algoritmusok helyett iteratív megoldásokban, kifejezések kiértékelésére (pl. fordított lengyel jelölés), hívásverem szimulációra, undo/redo megoldásokhoz stb.

---

1. Alapműveletek

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.

---

2. Implementációs lehetőségek

2.1. Dinamikus tömb (array‐backed)

• 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[initial]), cap(initial), topIndex(0) {}
      void push(const T& x) {
          if(topIndex == cap) resize(cap*2);
          data[topIndex++] = x;
      }
      void pop() { if(topIndex>0) --topIndex; }
      T& top() { return data[topIndex-1]; }
      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).

2.2. Láncolt lista (linked list)

• 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).
  • Tetszőleges méret, nincs átméretezés.

---

3. Nyelvek és könyvtárak

• 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[-1]
  stack.pop()
  empty = not stack
  

---

4. Tipikus felhasználási minták

1. Rekurzió szimuláció Ha nem használhatunk beépített rekurziót, a saját veremünkkel tarthatjuk a hívási kereteket.
2. Számítási kifejezések kiértékelése
   • Infix → Postfix (Shunting‐Yard algoritmus)
   • Postfix (Reverse Polish Notation) kiértékelés.
3. Visszalépéses (backtracking) algoritmusok Labirintus‐bejárás, kombinatorikus keresők (N‐királynő, Sudoku).
4. Undo/Redo mechanizmusok Grafikus alkalmazásokban a műveletek verembe kerülnek, undo‐kor pop, redo‐kor push.
5. Szélességi/mélységi keresés DFS (Depth‐First Search) iteratív implementációja veremmel.

---

5. Mire figyeljünk?

• Memória‐igény
  • Tömbnél előre kell választani kapacitást, vagy folyamatosan újraallokálni.
  • Láncolt listánál minden elem overhead-je: a pointer + objektum.
• Amortizált vs. garantált teljesítmény
  • Láncolt lista mindig O(1).
  • Tömb alapú esetén ritkán O(n) is lehet (resize), de átlagosan O(1).
• Kivételkezelés
  • Ha pop/top üres veremnél hívódik, kezelendő (hiba, kivétel, vagy guard condition).

---

Összefoglalás

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.

További információk

• stack data type - Szótár.net (en-hu)
• stack data type - Sztaki (en-hu)
• stack data type - Merriam–Webster
• stack data type - Cambridge
• stack data type - WordNet
• stack data type - Яндекс (en-ru)
• stack data type - Google (en-hu)
• stack data type - Wikidata
• stack data type - Wikipédia (angol)